//给你一个二叉树的根节点 root ， 检查它是否轴对称。 
//
// 
//
// 示例 1： 
// 
// 
//输入：root = [1,2,2,3,4,4,3]
//输出：true
// 
//
// 示例 2： 
// 
// 
//输入：root = [1,2,2,null,3,null,3]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [1, 1000] 内 
// -100 <= Node.val <= 100 
// 
//
// 
//
// 进阶：你可以运用递归和迭代两种方法解决这个问题吗？ 
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 2504 👎 0


package LeetCode.editor.cn;

import java.util.LinkedList;

/**
 * @author ldltd
 * @date 2023-08-16 23:00:58
 * @description 101.对称二叉树
 */
public class SymmetricTree {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new SymmetricTree().new Solution();

    }

    //力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
// Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        /*递归，时间空间on*/
        public boolean isSymmetric(TreeNode root) {
            if(root==null) {
                return true;
            }
            return isSyn(root.left, root.right);
        }

        private boolean isSyn(TreeNode l, TreeNode r) {
            if(l==null||r==null){
                return r==null&&l==null;
            }else if (l.val == r.val && isSyn(l.left, r.right) && isSyn(l.right, r.left))
                return true;
            else {
                return false;
            }
        }
        /*队列实现*/
        public boolean isSymmetric1(TreeNode root) {
            if(root==null || (root.left==null && root.right==null)) {
                return true;
            }
            //用队列保存节点
            LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
            //将根节点的左右孩子放到队列中
            queue.add(root.left);
            queue.add(root.right);
            while(queue.size()>0) {
                //从队列中取出两个节点，再比较这两个节点
                TreeNode left = queue.removeFirst();
                TreeNode right = queue.removeFirst();
                //如果两个节点都为空就继续循环，两者有一个为空就返回false
                if(left==null && right==null) {
                    continue;
                }
                if(left==null || right==null) {
                    return false;
                }
                if(left.val!=right.val) {
                    return false;
                }
                //将左节点的左孩子， 右节点的右孩子放入队列
                queue.add(left.left);
                queue.add(right.right);
                //将左节点的右孩子，右节点的左孩子放入队列
                queue.add(left.right);
                queue.add(right.left);
            }

            return true;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
